/*
 * Project: BoboDesignPattern
 * 
 * File Created at 2020年2月27日
 * 
 * Copyright 2012 Greenline.com Corporation Limited.
 * All rights reserved.
 *
 * This software is the confidential and proprietary information of
 * Greenline Company. ("Confidential Information").  You shall not
 * disclose such Confidential Information and shall use it only in
 * accordance with the terms of the license agreement you entered into
 * with Greenline.com.
 */
package test.lesson9.leetcode;

/**
 * @Type T2020227_53
 * @Desc 198. 打家劫舍 难度 简单
 * 
 *       650
 * 
 *       收藏
 * 
 *       分享 切换为英文 关注 反馈
 *       你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，
 *       如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
 * 
 *       给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
 * 
 *       示例 1:
 * 
 *       输入: [1,2,3,1] 输出: 4 解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
 *       偷窃到的最高金额 = 1 + 3 = 4 。 示例 2:
 * 
 *       输入: [2,7,9,3,1] 输出: 12 解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5
 *       号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12 。
 * @author 52489
 * @date 2020年2月29日
 * @Version V1.0
 */
public class T2020229_198 {

    public static void main(String[] args) {
        int nums[] = { 2, 7, 9, 3, 1 };
        System.out.println(robDP(nums));
        ;
    }

    public static int[] result;

    public int solve(int index, int[] nums) {
        if (index < 0) {
            return 0;
        }

        if (result[index] >= 0) {
            return result[index];
        }

        result[index] = Math.max(nums[index] + solve(index - 2, nums), solve(index - 1, nums));
        return result[index];
    }

    // 自顶向下的递归做法
    public int rob(int[] nums) {
        result = new int[nums.length];
        for (int i = 0; i < result.length; i++) {
            result[i] = -1;
        }
        return solve(nums.length - 1, nums);
    }

    // 动态规划做法
    public static int robDP(int[] nums) {
        if (nums.length == 0)
            return 0;
        int[] dp = new int[nums.length + 1];
        dp[0] = 0;
        dp[1] = nums[0];
        for (int i = 2; i <= nums.length; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
        }
        return dp[nums.length];
    }
}
